1. Field of the Invention
The present invention relates to a graphics processing apparatus for drawing graphics, text expressed in outline data, or the like in order to output the data to a printer, a display apparatus, or the like.
2. Description of the Related Art
In an editor, a CAD/CAM system, or the like which uses graphics or text expressed by outline data, in order to output the graphics or text to a printer or a display apparatus, a process of drawing the graphics is executed. The drawing process is performed by using, for example, blocks as shown in FIG. 2.
In FIG. 2, when a command of drawing the graphics or text is inputted by the-user or from the outside, the command is interpreted by a command interpretation unit 1 and is supplied to a vector data generation unit 2. In the case of the text, the vector data generation unit 2 sends a request to a font management unit 3 and acquires vector data expressing the outline of the text. A stroke (line) figure is converted to vector data, for example, as shown in FIG. 3 on the basis of the thickness and the shape of a connecting part. The text, stroke figure, or filled (painted) graphics converted as mentioned above is inputted to a display list generation unit 4.
The display list generation unit 4 first approximates a curved part expressed by a Bezier curve, spline, or the like to short straight lines and converts it into vector data of a polygon as shown in FIG. 4. Then, the display list generation unit 4 converts the vector data into an expression in a display list form as shown in FIG. 7. As an example of data regarding the vectors constructing a polygon, the display list has four pieces of element data of Dir: a direction flag (+1 in the case of upward orientation and xe2x88x921 in the case of downward) Xs: X coordinate of the vector start point, Ye: Y coordinate of the vector end point, and Dx: a change amount (gradient) of X with respect to increase of +1 in the Y coordinate. The conversion from the polygon to the display list will be further described in detail hereinafter.
The display list data generated as described above is supplied to a display list drawing unit 13. The display list drawing unit 13 calculates the coordinates of an intersecting point of each of the sides in the inputted display list and each scan line of an output device by a method of a DDA (Digital Differential Analyzer) or the like, sorts the data on the basis of the X coordinate values every scan line, obtains the correspondence between the start point and end point of a fill part, and draws a line segment parallel to the scan line corresponding to the interval on a memory unit 14. The memory data drawn as mentioned above is transferred to an output device 15 such as a printer or display apparatus, thereby performing printing or display.
In such a graphics drawing process, the operation of the display list drawing unit 13 is xe2x80x9cheavyxe2x80x9d since DDA, sorting, drawing on the memory, and the like of each side are included. Especially, in the case of drawing complicated graphics including overlaps such as gradation, overwriting occurs many times in the same memory area and it is a main factor of deterioration in processing speed as a whole. Further, like a printer of recent years, in the case of reducing a page memory by accumulating a drawing command at the level of a polygon, a display list, an edge list, or the like and outputting the data while forming an image in a real time manner in accordance with the printing speed of the printer, there is a problem (hereinbelow, also called a first problem) such that an image formation is not performed in time in a complicated part where there are many overlaps and a picture dropout may occur.
Since the operation of the display list drawing unit 13 is heavy, a high-speed process is intended by dedicated hardware. Although the process is relatively simple in the case of a polygon having projected parts as shown in FIG. 5A, in the case where recessed parts are included as shown in FIG. 5B or in the case where the intersections of sides as illustrated in FIG. 5C are included, plural pairs of the start and end points exist in each scan line. Consequently, a process of sorting the intersections obtained as mentioned above and finding the correspondence is necessary. In the case where there is no restriction in the complication of the graphics inputted, however, the number of intersections is not limited, so that a problem (hereinbelow, also called a second problem) such that it is very difficult to construct a sorting circuit by hardware arises.
As an attempt of solving the first problem, a method of increasing the speed of the process and performing a real-time drawing by eliminating overlapped parts from the drawing elements has been conventionally proposed. Japanese Published Unexamined Patent Application Nos. Hei 8-279050, Hei 9-62851, Hei 9-171563, Hei 9-281953, and the like are conventional arts based on the idea.
As an attempt of solving the second problem, there is a method of dividing a polygon into figures such as trapezoids (including square and triangle) each having the bottom side parallel to the X axis in which no sorting occurs and processing each of the figures. Japanese Published Unexamined Patent Application Nos. Sho 60-74086, Sho 61-248176, Sho 62-271186, and the like are conventional arts based on the idea.
According to the methods of the Japanese Published Unexamined Patent Application Nos. Hei 8-279050 and Hei 9-62851, the drawing element is stored in the form of the edge list, and when the edge information of drawing for the same scan line is compared with each other and there is an overlap, the overlap is removed. The data amount of the drawing elements to be stored in the edge list is enormous when the resolution is high as in the printer of recent years, so that there is a drawback such that the cost of the memory increases.
According to the methods of Japanese Published Unexamined Patent Application Nos. Hei 9-171563 and Hei 9-281953, the drawing element is stored in the form of polygon data and an overlap of two polygons is checked. When there is an overlap, it is removed. In order to remove the overlap at the polygon level, however, the polygon has to have simple projected parts. For a polygon including a recessed part and an intersection of sides, a preliminary process of dividing the polygon into figures having projections is necessary. Although the object is narrowed down by the overlap determination, overlay graph, or the like, since a method of basically removing an overlap of two polygons is used, processes of N! (factorial of N) times are necessary to completely remove the overlaps of N process targets.
The present invention has been achieved in consideration of the problems of the conventional arts as mentioned above. The present invention provides a high speed graphics processing apparatus having an overlap removal part for removing an overlap of drawing elements expressed in a display list format, capable of storing data in a small memory amount even when the resolution is higher as compared with an edge list and removing an overlap by a small amount of process without performing a special preliminarily process.
In the Japanese Published Unexamined Patent Application Nos. Sho 60-74086 and Sho 61-248176, a polygon is divided into trapezoids (including square and triangle) each having the bottom side parallel to the X axis and the trapezoids are sequentially processed, thereby making a sorting circuit at the time of a filling process unnecessary. According to the method, however, since a number of trapezoids are generated when a complicated polygon is divided, it is difficult to control or temporarily store the trapezoids and there is also a problem that the processing speed is low since the process is performed every trapezoid.
In the Japanese Published Unexamined Patent Application No. Sho 62-271186, an inputted figure including a curve is divided into partial figures so as to have one drawing line segment at each scan line, the partial figures are inputted to plural DDA circuits and line segment drawing circuits, and processes are performed in parallel. According to the method, however, the number of divided figures changes according to the complexity of the inputted figure, so that the necessary number of DDA circuits/line segment drawing circuits cannot be regulated. Since the partial figures are drawn on different scan lines, it can be presumed that competition occurs at the time of writing data into a memory and the processing speed is not raised.
In order to solve such problems, the inventors of the present invention have proposed in Japanese Patent Published Unexamined Patent Application No. Hei 11-144066a graphics processing apparatus having 2N (N is 1 or larger) DDA parts, a sorting part capable sorting 2N inputs, and a division part for dividing an inputted arbitrary display list into plural display lists so that the number of drawing line segments in each scan line becomes N or smaller, which can execute a process at high speed and can control and store divided graphics in an area as small as possible by dividing a display list expressing a polygon inputted into partial polygons which can be subjected to the DDA and sorting.
In the method proposed in Japanese Published Unexamined Patent Application No. Hei 11-144066, the part corresponding to the display list drawing unit can draw only the drawing element. In a drawing command, however, a clip element for regulating the area in which the drawing element is drawn on a memory is also included. In this case, the drawing element has to be clipped by the clip element until it is inputted to the display list drawing unit, so that there is a case that the speed is decreased.
As a countermeasure against the problem, it can be considered that the construction of the display list drawing unit is changed so that the display list information in which the drawing element and the clip element mixedly exist can be inputted and the drawing operation can be performed while clipping the drawing element. The method of dividing the display list has been proposed in Japanese Published Unexamined Patent Application No. Hei 11-144066, however, cannot deal with mixed elements. When a scan line on which the number of sides is larger than 2N exists, a complicated process of once separating the clip element and the drawing element from each other, performing the dividing process described in Japanese Published Unexamined Patent Application No. Hei 11-144066separately to the clip element and the drawing element, and allowing the clip and drawing elements to exist mixedly is necessary. There is consequently a drawback such that the whole performance deteriorates.
The present invention has been achieved in consideration of the above points. The present invention also provides a graphics processing apparatus which can control and store a divided figure in an area as small as possible even when a clip element and a drawing element mixedly exist and can execute a process at high speed.
According to the present invention, the graphics processing apparatus for drawing graphics has a display list generation part that converts vector information (for example, which designates the shape and a drawing color of the drawing element and the clip element and the type of the figure such as a stroke figure or fill figure and expresses attributes such as the line width and the kind of the line when the figure is the stroke figure) describing a drawing element or a clip element of graphics into straight line vector information obtained by approximating a polygon to a shape of vectors constructing the drawing element or clip element, sorts the straight line vectors included in the straight line vector information on the basis of vector start scan line coordinate values, and generates a display list constructed of information including the direction and gradient of each of the straight line vectors and the number of scan lines crossed or data equivalent to those information, a merge process part which merges a display list indicative of the drawing element with a display list indicative of the clip element for restricting a drawing area of the drawing element which are generated by the display list generation part, thereby generating a display list in which the drawing element and the clip element mixedly exist, a display list storage part for storing the display list, a determination part for checking to see whether or not the number of straight line vectors which cross a scan line is equal to or smaller than 2N (N is an integer of 1 or larger) in all of scan lines on the basis of the display list, a clip process part for clipping the drawing element by the clip element with respect to the display list in which the clip element and the drawing element mixedly exist, thereby converting the display list to a display list having only drawing elements, a division process part for dividing the display list having only the drawing elements converted by the clip process part so that the number of straight line vectors which cross all of the scan lines becomes equal to or smaller than 2N, thereby generating plural display lists, an overlap removal part for generating a new display list obtained by removing an overlap of drawing areas from plural display lists having the overlap in the drawing areas, a display list drawing part having 2N DDA parts each for calculating the coordinate value of an intersection between each scan line and the straight line vector on the basis of the display list, a sorting part for sorting output values from the DDA parts, and a memory drawing part that obtains position information of a start point and an end point of a drawing line segment from the data sorted by the sorting part and fills a memory area between the start and end points, and an overlap removal determination part for estimating processing time of drawing the display list by the display list drawing part and determines an effect of executing the overlap removing process by the overlap removal part on the basis of the estimated drawing processing time.
According to the construction, the high-speed graphics processing apparatus having the overlap removal part of removing an overlap of drawing elements expressed in the display list format, which can store data in a small memory amount even when the resolution is higher as compared with an edge list and can remove an overlap by a small amount of process without performing a special preliminary process can be realized. Further, the high-speed graphics processing apparatus in which the overlap removing process is minimized by containing the determination part for determining whether the overlap removing process is necessary or not and the clip process part for clipping the display list in which the clip element and the drawing element mixedly exist and converting the display list into a display list having only drawing elements, and which can deal with the case where the clip element and the drawing mixedly exist can be realized. Further, the high-speed graphics processing apparatus can be realized which can divide the display list when the number of drawing elements to be drawn finally exceeds 2N (N is a positive integer), control and store drawing data in a small area, and control and store divided figures in an area as small as possible even when the clip element and the drawing element mixedly exists.
Further, according to the present invention, there is also provided a graphics processing apparatus for drawing graphics having a display list generation part that converts vector information describing a drawing element or a clip element of graphics into straight line vector information obtained by approximating a polygon to a shape of vectors constructing the drawing element or clip element, sorts straight line vectors included in the straight line vector information on the basis of vector start scan line coordinate values, and generates a display list constructed of information including the direction and gradient of each of the straight line vectors and the number of scan lines which are crossed or data equivalent to those information, a merge process part which merges a display list indicative of the drawing element with a display list indicative of the clip element for restricting a drawing area of the drawing element which are generated by the display list generation part, thereby generating a display list in which the drawing element and the clip element mixedly exist, a determination part for checking to see whether or not the number of straight line vectors which cross a scan line is equal to or smaller than 2N (N is an integer of 1 or larger) in all of scan lines on the basis of the display list, a clip process part for clipping the drawing element by the clip element with respect to the display list in which the clip element and the drawing element mixedly exist, thereby converting the display list to a display list having only drawing elements, a division process part for dividing the display list having only the drawing elements converted by the clip process part so that the number of straight line vectors which cross all of the scan lines becomes equal to or smaller than 2N, thereby generating plural display lists, and a display list drawing part having 2N DDA parts each for calculating the coordinate value of an intersection between each scan line and the straight line vector on the basis of the display list, a sorting part for sorting output values from the DDA parts, and a memory drawing part that obtains position information of a start point and an end point of a drawing line segment from the data sorted by the sorting part and fills a memory area between the start and end points.
According to the construction as well, the high-speed graphics processing apparatus which can deal with the case where the clip element and the drawing mixedly exist by having the clip process part for clipping the display list in which the clip element and the drawing element mixedly exist, thereby converting the display list to a display list having only drawing elements can be realized. Further, the high-speed graphics processing apparatus can be realized which can divide the display list when the number of drawing elements to be drawn finally exceeds 2N (N is a positive integer), control and store drawing data in a small area, and control and store divided figures in an area as small as possible even when the clip element and the drawing element mixedly exists.
Further, according to the present invention, a graphics processing apparatus for drawing graphics has a display list generation part that converts vector information describing a drawing element or a clip element of graphics into straight line vector information obtained by approximating a polygon to a shape of vectors constructing the drawing element or clip element, sorts the straight line vectors included in the straight line vector information on the basis of vector start scan line coordinate values, and generates a display list constructed of information including the direction and gradient of each of the linear vectors and the number of scan lines crossed or data equivalent to those information, a merge process part which merges a display list indicative of the drawing element with a display list indicative of the clip element for restricting a drawing area of the drawing element which are generated by the display list generation part, thereby generating a display list in which the drawing element and the clip element mixedly exist, a display list storage part for storing the display list, a clip process part for clipping the drawing element by the clip element with respect to the display list in which the clip element and the drawing element mixedly exist, thereby converting the display list to a display list having only drawing elements, an overlap removal part for generating a new display list by removing an overlap of drawing areas from plural display lists having the overlap in the drawing areas, a display list drawing part for drawing graphics expressed by the display lists, and an overlap removal determination part for estimating processing time of drawing the display list by the display list drawing part and determining the execution effect of the overlap removing process by the overlap removal part on the basis of the estimated drawing processing time.
According to the construction, the high-speed graphics processing apparatus having the overlap removal part for removing an overlap in drawing elements expressed in the display list format, capable of storing data in a small memory amount even when the resolution is higher as compared with an edge list and removing an overlap with a small amount of process without performing a special preliminary process can be realized. Further, the high-speed graphics processing apparatus can be realized which minimizes the overlap removing process and can deal with the case where the clip element and the drawing element mixedly exist by having the determination part for determining whether the overlap removing process is necessary or not and the clip process part for clipping the display list in which the clip element and the drawing element mixedly exist to thereby convert the display list into a display list having only the drawing elements.
Further, according to the present invention, a graphics processing apparatus for drawing graphics has a display list generation part that converts vector information describing a drawing element or a clip element of graphics into straight line vector information obtained by approximating a polygon to a shape of vectors constructing the drawing element or clip element, sorts the straight line vectors included in the straight line vector information on the basis of vector start scan line coordinate values, and generates a display list constructed of information including the direction and gradient of each of the straight line vectors and the number of scan lines crossed or data equivalent to the above information, a display list storage part for storing the display list, a clip process part for clipping the drawing element by the clip element with respect to the display list which expresses the clip element and the drawing element, an overlap removal part that generates a new display list by removing an overlap of drawing areas from plural display lists having the overlap in the drawing areas, and a display list drawing part for drawing graphics expressed by the display lists.
According to the construction as well, the high-speed graphics processing apparatus having the overlap removal part for removing an overlap in drawing elements expressed in the display list format, capable of storing data in a small memory amount even when the resolution is higher as compared with an edge list and removing an overlap with a small amount of process without performing a special preliminary process can be realized. Further, the high-speed graphics processing apparatus can be realized which can deal with the case where the clip element and the drawing element mixedly exist by having the clip process part for clipping the display list in which the clip element and the drawing element mixedly exist to thereby convert the display list into a display list having only the drawing elements.
Further, according to the present invention, a graphics processing apparatus for drawing graphics has a display list generation part that converts vector information describing a drawing element of graphics into straight line vector information obtained by approximating a polygon to a shape of vectors constructing the drawing element, sorts the straight line vectors included in the straight line vector information on the basis of vector start scan line coordinate values, and generates a display list constructed of information including the direction and gradient of each straight line vector and the number of scan lines crossed or data equivalent to the above information, a display list storage part for storing the display list, an overlap removal part that generates a new display list by removing an overlap of drawing areas from plural display lists having the overlap in the drawing areas, and a display list drawing part for drawing graphics expressed by the display lists.
According to the construction, the high-speed graphics processing apparatus having the overlap removal part for removing an overlap in drawing elements expressed in the display list format, capable of storing data in a small memory amount even when the resolution is higher as compared with an edge list and removing an overlap with a small amount of process without performing a special preliminary process can be realized.
Further, the graphics processing apparatus of the present invention may have an overlap removal determination part which estimates processing time of a process of drawing the display list by the display list drawing part and determines an effect of executing the overlap removing process by the overlap removal part on the basis of the estimated drawing processing time.
The graphics processing apparatus of the present invention may have an area division process part for dividing an output area of the display list into partial areas and performs a process for every partial area.
In the graphics processing apparatus of the present invention, the merge process part may set a value indicative of a vector direction in a display list related to a straight line vector constructing the drawing element and a value indicative of a vector direction in a display list related to a straight line vector constructing the clip element so as to be different from each other in the mixed display list to be generated.
Further, in the graphics processing apparatus of the present invention, the merge process part can obtain at least one of or both of a common Y coordinate range and a common X coordinate range from circumscribed rectangles of the display list indicative of the drawing element and the display list indicative of the clip element and generate a mixed display list constructed by a straight line vector restricted within the common coordinate range.
According to the graphics processing apparatus of the present invention, the determination part reads the straight line vectors included in the display list in accordance with the order from the smaller start scan line coordinate value, holds an end scan line coordinate value of the straight line vector, discards the end scan line coordinate value held when the start scan line coordinate value of the read straight line vector is larger than the end scan line coordinate value which has already been held, outputs a determination result that the number of end scan line coordinate values is not equal to or smaller than 2N at the time point when the number of end scan line coordinate values held becomes larger than 2N and outputs a determination result that the number of end scan line coordinate values is equal to or smaller than 2N at the time point when the sum of the number of straight line vectors which are not yet read and the number of end scan line coordinate values held becomes equal to or smaller than 2N.
In the graphics processing apparatus of the present invention, a converting process into a display list having only the drawing elements by the clipping process by the clip process part may be executed to the mixed display list to be subjected to the overlap removing process when it is determined by the overlap removal determination part that the overlap removing process is necessary.
Further, in the graphics processing apparatus of the present invention, the converting process into a display list having only the drawing elements by the clipping process by the clip process part may be executed under the conditions that
a) the display list is determined by the determination part that a scan line which is crossed by the straight line vectors larger than N2 exists and
b) the display list is a display list in which the drawing element and the clip element mixedly exist.
Further, in the graphics processing apparatus of the present invention, a process of dividing a display list so that the number of straight line vectors which cross all of scan lines becomes equal to or smaller than 2N and thereby generating plural display lists in the division process part may be executed under the conditions that
c) the display list is determined by the determination part that a scan line which is crossed by the straight line vectors larger than N2 exists and
d) the display list has only drawing elements.
In the graphics processing apparatus of the present invention, the overlap removal part may sequentially take a display list corresponding to a drawing element in an upper layer to be displayed or printed on the most front face and then a display list corresponding to a drawing element in a lower layer from the display list storage part and perform the overlap removing process on the basis of the taken display lists corresponding to the plural drawing elements.
Further, in the graphics processing apparatus of the present invention, the overlap removal part may generate a merged area display list indicative of the whole drawing area of plural drawing elements to be subjected to the overlap removing process and perform a new overlap removing process on a display list newly taken from the display list storage part.
In the graphics processing apparatus of the present invention, the determination by the overlap removal process determination part may be performed for every partial area obtained by the dividing operation of the area division process part and whether the overlap removing process is performed or not may be changed for every partial area.
In the graphics processing apparatus of the present invention, the overlap removal determination part may obtain an estimated value of drawing time in the display list drawing part by using information of at least one of the drawing area of the display list, a circumscribed rectangle area, or the height.
Further, in the graphics processing apparatus of the present invention, an estimated value of drawing time in the display list drawing part obtained by the overlap removal determination part may be derived by a drawing process time estimation calculating method according to drawing element attributes including information indicating that the drawing element is text, graphics, or an image.
Further, in the graphics processing apparatus of the present invention, the overlap removal determination part obtains the estimated value of the drawing process time in the display list drawing part on the basis of the result of the process by the overlap removal part, when the estimated value of the drawing process time based on the obtained process result is equal to or smaller than a predetermined threshold value, a new overlap removing process by the overlap removal part may not be executed.
In the graphics processing apparatus of the present invention, the process by the overlap removal part may be executed for every divided group obtained by dividing the display list corresponding to plural drawing elements to be processed into plural groups.
In the graphics processing apparatus of the present invention, the process by the overlap removal part may be executed every partial area in plural partial areas obtained by dividing a drawing area to be processed.
In the graphics processing apparatus of the present invention, the memory drawing part may change a method of calculating position information of a start point and an end point of a line segment to be drawn from the sorted data on the basis of conditions that the display list to be processed is a display list having only drawing elements or a mixed display list in which the drawing element and the clip element mixedly exist and a fill rule of the drawing element and the clip element in the display list to be processed is an even-odd rule or non-zero winding number rule.
In the graphics processing apparatus of the present invention, the 2N DDA parts have a construction such that processes can be performed in parallel and a process of calculating the coordinate value of the intersection between each scan line and a straight line vector may be executed by a parallel process.
In the graphics processing apparatus, the process by the overlap removal part can be performed in such a manner that plural drawing elements to be processed are actually drawn in accordance with the order from the lower layer so as to be converted to image drawing elements, the processing time of drawing the image drawing elements and the remaining drawing elements by the display list drawing part is estimated by the overlap removal determination part, and the conversion to the image drawing element can be performed until it is determined that the overlap removing process is unnecessary.
Further, in the graphics processing apparatus of the present invention, the process by the overlap removal part can be performed in such a manner that a drawing area to be processed is divided into plural partial areas, some partial areas divided are actually drawn so as to be converted to image drawing elements, the processing time of drawing the image drawing elements and the drawing elements included in the remaining partial areas by the display list drawing part is estimated by the overlap removal determination part, and the sequential conversion from the plural partial areas to the image drawing elements can be performed until it is determined that the overlap removing process is unnecessary.
Further, in the graphics processing apparatus of the present invention, the estimated value of drawing processing time by the display list drawing part obtained by the overlap removal determination part can also be derived by using area approximation value information obtained by performing a process corresponding to a display list drawing process at resolution lower than required resolution.
In the graphics processing apparatus of the present invention, when a figure is a stroke figure, the display list generation part obtains an approximation value of the drawing area on the basis of information such as the stroke length, line width, and kind of line of each vector and may add the approximation value information of the drawing area to the display list generated from the stroke figure.
In the graphics processing apparatus of the present invention, when a figure is a fill figure, the display list generation part at least determines whether the fill figure has a self intersection or not and whether the fill figure is constructed of plural separated graphics elements. When the fill figure does not have a self intersection and is constructed of single graphics elements, an approximation value of the drawing area is obtained on the basis of straight line vectors constructing the figure and approximation value information of the drawing area may be added to the display list generated from the fill figure.
In the graphics processing apparatus of the present invention, the clip process part has a part for determining at least whether the shape of a graphics element is a rectangle or not, and may change the clipping method on the basis of the result of the determination by the determination part.